There exists a class of server and other applications that access their data as “blocks,” or contiguous chunks of memory of a fixed size. The server applications include, but are not limited to, file systems, databases, email, and directories. Usually, the server applications need to access far more data than can be held in the memory of the machine (“host machine”) hosting the respective server application. As a result, many of these server applications choose to cache a portion of their data in memory, typically using some form of a block cache.
Due to the large number of possible host machine configurations on the market, it is not practical to statically determine an optimal size for a block cache for a server application at application coding time. Thus, many server applications make a decision at install time or run time as to the size of the block cache. Because the size of the block cache can have a dramatic impact on the performance of the server, the decision regarding the size of the block cache is an important one. Unfortunately, such a decision is usually very technical and fraught with details, such as the current and future configuration of the hardware and software of the host machine. These details render simplistic install time algorithms ineffective in general. In addition, taking such details into account requires that any run time tuning be done by a person with technical skills that exceed that of the typical server administrator. An even higher degree of difficulty occurs if the host machine hosts multiple different server applications that each contain such a block cache.
There have been many attempts to size caches using a variety of different algorithms. For example, an operating system might balance its file cache against its processes by regarding the file cache as a process with a working set. The operating system can then use an algorithm, such as the standard working set clock algorithm, to manage the size of the file cache along with the other processes. This system works fairly well, but a user mode application with a cache that is a subset of its own working set cannot take advantage of this behavior. Further, treating the cache as a process with a working set inextricably links the cache replacement policy with the cache sizing policy.
Another way to establish cache size is to permit the cache to take all available virtual memory except a fixed amount. This method may be used, for example, by a server application. If new applications startup, the cache for the server application will free memory as it is used by the new applications. One problem with this system is that if too many other applications startup, then the cache for the server application can be reduced to zero. Further, if more than one server application is running at the same time, then the size of the cache for each of the server applications will not always converge to a stable size under steady state load. Even worse, it is possible for such a solution to “runaway” by consuming memory indefinitely if a significant portion of its host process is paged out by the operating system.